package com.platform.modules.alg.alglib.hdu2586;

public class Hdu2586 {
    private int maxn = 40005;
    int n, m; // n 个结点，m 个查询
    int head[] = new int[maxn]; // 头结点
    int dist[] = new int[maxn]; // 距离
    int cnt;
    int fa[] = new int[maxn]; // 父亲
    int dep[] = new int[maxn]; // 深度
    int size[] = new int[maxn]; // 子树结点总数
    int son[] = new int[maxn]; // 重儿子
    int top[] = new int[maxn]; // 所在重链顶端结点
    public String output = "";
    Edge e[] = new Edge[maxn << 1];

    public String cal(String input) {
        int a, b, lca;
        String[] line = input.split("\n");
        String[] words = line[0].split(" ");
        n = Integer.parseInt(words[0]);
        m = Integer.parseInt(words[1]);

        for (int i = 1; i <= n; i++) // 初始化
            head[i] = dep[i] = dist[i] = son[i] = 0;
        cnt = 0;
        for (int i = 1; i < n; i++) { // 输入一棵树的 n-1 边
            int x, y, z;
            String[] info = line[i].split(" ");
            x = Integer.parseInt(info[0]);
            y = Integer.parseInt(info[1]);
            z = Integer.parseInt(info[2]);
            add(x, y, z);
            add(y, x, z);
        }
        dep[1] = 1;
        dfs1(1, 0);
        dfs2(1);
        for (int i = 1; i <= m; i++) {
            String[] query = line[n - 1 + i].split(" ");
            a = Integer.parseInt(query[0]);
            b = Integer.parseInt(query[1]);
            lca = LCA(a, b);
            // 输出x y的距离
            output += dist[a] + dist[b] - 2 * dist[lca] + "\n";
        }
        return output;
    }

    void add(int u, int v, int w) {
        e[++cnt].to = v;
        e[cnt].c = w;
        e[cnt].next = head[u];
        head[u] = cnt;
    }

    // 求 dep,fa,size,son,dist
    void dfs1(int u, int f) {
        size[u] = 1;
        for (int i = head[u]; i > 0; i = e[i].next) {
            int v = e[i].to;
            if (v == f) // 父节点
                continue;
            dep[v] = dep[u] + 1; // 深度
            fa[v] = u;
            dist[v] = dist[u] + e[i].c; // 距离
            dfs1(v, u);
            size[u] += size[v];
            if (size[v] > size[son[u]])
                son[u] = v;
        }
    }

    // 求 top
    void dfs2(int u) {
        if (u == son[fa[u]])
            top[u] = top[fa[u]];
        else
            top[u] = u;
        for (int i = head[u]; i > 0; i = e[i].next) {
            int v = e[i].to;
            if (v != fa[u])
                dfs2(v);
        }
    }

    // 求 u,v 的最近公共祖先
    int LCA(int u, int v) {
        while (top[u] != top[v]) { // 不在同一条重链上
            if (dep[top[u]] > dep[top[v]])
                u = fa[top[u]];
            else
                v = fa[top[v]];
        }
        return dep[u] > dep[v] ? v : u; // 返回深度小的结点
    }

    public Hdu2586() {
        for (int i = 0; i < e.length; i++) {
            e[i] = new Edge();
        }
    }
}


class Edge {
    int to, c, next;
}
